<!DOCTYPE html>
<html>
<head>
    <meta charset="utf-8" >

<title>每日一题20210306（503. 下一个更大元素 II） | 小克的blog</title>

<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1, user-scalable=no">

<link rel="stylesheet" href="https://use.fontawesome.com/releases/v5.7.2/css/all.css" integrity="sha384-fnmOCqbTlWIlj8LyTjo7mOUStjsKC4pOpQbqyi7RrhN7udi9RwhKkMHpvLbHG9Sr" crossorigin="anonymous">
<link rel="shortcut icon" href="https://woodywrx.gitee.io/blog/favicon.ico?v=1615823433634">
<link rel="stylesheet" href="https://woodywrx.gitee.io/blog/styles/main.css">



<link rel="stylesheet" href="https://unpkg.com/aos@next/dist/aos.css" />
<script src="https://cdn.jsdelivr.net/npm/vue/dist/vue.js"></script>



    <meta name="description" content="503. 下一个更大元素 II

想法
首先和大部分人想的一样，第一反应也是想着用暴力法，复杂度是O(n²)
所以我坐在公交车🚌开始想新的解法，但也只能想出稍微优化的解法，比如[2, 1, 1, 3] 如果找到2的下一个最大值，那么后面的..."/>
    <meta name="keywords" content=""/>
</head>
<body>

<div id="app" class="main">

    <div class="sidebar" :class="{ 'full-height': menuVisible }">
  <div class="top-container" data-aos="fade-right">
    <div class="top-header-container">
      <a class="site-title-container" href="https://woodywrx.gitee.io/blog">
        <img src="https://woodywrx.gitee.io/blog/images/avatar.png?v=1615823433634" class="site-logo">
        <h1 class="site-title">小克的blog</h1>
      </a>
      <div class="menu-btn" @click="menuVisible = !menuVisible">
        <div class="line"></div>
      </div>
    </div>
    <div>
      
        
          <a href="https://woodywrx.gitee.io/blog" class="site-nav">
            首页
          </a>
        
      
        
          <a href="https://woodywrx.gitee.io/blog/tags" class="site-nav">
            标签
          </a>
        
      
        
          <a href="https://woodywrx.gitee.io/blog/post/about" class="site-nav">
            关于
          </a>
        
      
    </div>
  </div>
  <div class="bottom-container" data-aos="flip-up" data-aos-offset="0">
    <div class="social-container">
      
        
      
        
      
        
      
        
      
        
      
    </div>
    <div class="site-description">
      欢迎来到我的小窝~这里不仅有博客，也有日记。
    </div>
    <div class="site-footer">
      wuranxu's blog | <a class="rss" href="https://woodywrx.gitee.io/blog/atom.xml" target="_blank">RSS</a>
    </div>
  </div>
</div>


    <div class="main-container">
        <div class="content-container" data-aos="fade-up">
            <div class="post-detail">
                <h2 class="post-title">每日一题20210306（503. 下一个更大元素 II）</h2>
                <div class="post-date">2021-03-06 13:13:20</div>
                
                <div class="post-content" v-pre>
                    <section id="nice" data-tool="mdnice编辑器" data-website="https://www.mdnice.com" style="padding: 0 10px; word-spacing: 0px; word-wrap: break-word; text-align: left; font-family: Optima-Regular, Optima, PingFangSC-light, PingFangTC-light, 'PingFang SC', Cambria, Cochin, Georgia, Times, 'Times New Roman', serif; line-height: 1.6; letter-spacing: .034em; color: rgb(63, 63, 63); font-size: 16px; word-break: all;"><h3 data-tool="mdnice编辑器" style="margin-bottom: 15px; padding: 0px; font-weight: bold; color: black; font-size: 20px; margin-top: 1.2em;"><span style="background-image: url(https://files.mdnice.com/koala-3.png); background-size: 100% 100%; background-repeat: no-repeat; display: inline-block; width: 16px; height: 15px; line-height: 15px; margin-bottom: -1px;"></span><span class="prefix" style="display: none;"></span><span class="content" style="font-size: 17px; font-weight: bold; display: inline-block; margin-left: 8px; color: #48b378;">503. 下一个更大元素 II</span><span class="suffix" style="display: none;"></span></h3>
<figure data-tool="mdnice编辑器" style="margin: 0; margin-top: 10px; margin-bottom: 10px; display: flex; flex-direction: column; justify-content: center; align-items: center;"><img src="https://imgkr2.cn-bj.ufileos.com/689ca3ac-9a83-479d-9545-bc28a4a4a314.png?UCloudPublicKey=TOKEN_8d8b72be-579a-4e83-bfd0-5f6ce1546f13&amp;Signature=ej%252BI56rLNdPfmC0WfMlvknJ65HM%253D&amp;Expires=1615090822" alt style="display: block; margin: 0 auto; max-width: 100%; border-radius: 4px; margin-bottom: 25px;"></figure>
<h3 data-tool="mdnice编辑器" style="margin-bottom: 15px; padding: 0px; font-weight: bold; color: black; font-size: 20px; margin-top: 1.2em;"><span style="background-image: url(https://files.mdnice.com/koala-3.png); background-size: 100% 100%; background-repeat: no-repeat; display: inline-block; width: 16px; height: 15px; line-height: 15px; margin-bottom: -1px;"></span><span class="prefix" style="display: none;"></span><span class="content" style="font-size: 17px; font-weight: bold; display: inline-block; margin-left: 8px; color: #48b378;">想法</span><span class="suffix" style="display: none;"></span></h3>
<p data-tool="mdnice编辑器" style="font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;">首先和大部分人想的一样，第一反应也是想着用暴力法，复杂度是O(n²)</p>
<p data-tool="mdnice编辑器" style="font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;">所以我坐在公交车🚌开始想新的解法，但也只能想出稍微优化的解法，比如[2, 1, 1, 3] 如果找到2的下一个最大值，那么后面的1也不需要继续找了，因为他们比2还小，所以他们的下一个最大值也是8。</p>
<p data-tool="mdnice编辑器" style="font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;">想到这里我的思路也就戛然而止了~</p>
<h3 data-tool="mdnice编辑器" style="margin-bottom: 15px; padding: 0px; font-weight: bold; color: black; font-size: 20px; margin-top: 1.2em;"><span style="background-image: url(https://files.mdnice.com/koala-3.png); background-size: 100% 100%; background-repeat: no-repeat; display: inline-block; width: 16px; height: 15px; line-height: 15px; margin-bottom: -1px;"></span><span class="prefix" style="display: none;"></span><span class="content" style="font-size: 17px; font-weight: bold; display: inline-block; margin-left: 8px; color: #48b378;">思路</span><span class="suffix" style="display: none;"></span></h3>
<p data-tool="mdnice编辑器" style="font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;">这种情况下，我们可以使用单调栈来解决问题。我们用一个栈去记录数组元素的下标（因为下标记住了，所以等于记住了这个下标元素的值）</p>
<ul data-tool="mdnice编辑器" style="margin-top: 8px; margin-bottom: 8px; padding-left: 25px; color: black; list-style-type: disc;">
<li><section style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; text-align: left; color: rgb(1,1,1); font-weight: 500;">当栈为空的时候，我们把下标直接压入栈。</section></li><li><section style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; text-align: left; color: rgb(1,1,1); font-weight: 500;">当栈不为空的时候，我们和栈的顶部元素进行对比:
<ul style="margin-top: 8px; margin-bottom: 8px; padding-left: 25px; color: black; list-style-type: square;">
<li><section style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; text-align: left; color: rgb(1,1,1); font-weight: 500;">如果当前元素比顶部元素小，那么直接入栈</section></li><li><section style="margin-top: 5px; margin-bottom: 5px; line-height: 26px; text-align: left; color: rgb(1,1,1); font-weight: 500;">如果当前元素大于顶部元素，顶部元素出栈，直到顶部元素比当前元素大为止</section></li></ul>
</section></li></ul>
<h4 data-tool="mdnice编辑器" style="margin-bottom: 15px; padding: 0px; font-weight: bold; color: black; font-size: 18px; margin-top: 30px;"><span class="prefix" style="display: none;"></span><span class="content">这样做的目的是为了保证栈是大的在上面，小的在下面，在找到比顶部元素大的数字的时候，就是顶部元素的下一个更大元素</span><span class="suffix" style="display: none;"></span></h4>
<h3 data-tool="mdnice编辑器" style="margin-bottom: 15px; padding: 0px; font-weight: bold; color: black; font-size: 20px; margin-top: 1.2em;"><span style="background-image: url(https://files.mdnice.com/koala-3.png); background-size: 100% 100%; background-repeat: no-repeat; display: inline-block; width: 16px; height: 15px; line-height: 15px; margin-bottom: -1px;"></span><span class="prefix" style="display: none;"></span><span class="content" style="font-size: 17px; font-weight: bold; display: inline-block; margin-left: 8px; color: #48b378;">注意点</span><span class="suffix" style="display: none;"></span></h3>
<p data-tool="mdnice编辑器" style="font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;">这里存在末尾元素，所以需要遍历数组2次，我们遍历的索引从0-2n即可，可以通过取余获取到当前元素的真实索引。</p>
<pre class="custom" data-tool="mdnice编辑器" style="margin-top: 10px; margin-bottom: 10px; border-radius: 5px; box-shadow: rgba(0, 0, 0, 0.55) 0px 2px 10px;"><span style="display: block; background: url(https://files.mdnice.com/point.png); height: 30px; width: 100%; background-size: 40px; background-repeat: no-repeat; background-color: #282c34; margin-bottom: -7px; border-radius: 5px; background-position: 10px 10px;"></span><code class="hljs" style="overflow-x: auto; padding: 16px; color: #abb2bf; display: -webkit-box; font-family: Operator Mono, Consolas, Monaco, Menlo, monospace; font-size: 12px; -webkit-overflow-scrolling: touch; padding-top: 15px; background: #282c34; border-radius: 5px;"><span class="hljs-class" style="line-height: 26px;"><span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">class</span>&nbsp;<span class="hljs-title" style="color: #e6c07b; line-height: 26px;">Solution</span>:</span><br>&nbsp;&nbsp;&nbsp;&nbsp;<span class="hljs-function" style="line-height: 26px;"><span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">def</span>&nbsp;<span class="hljs-title" style="color: #61aeee; line-height: 26px;">nextGreaterElements</span><span class="hljs-params" style="line-height: 26px;">(self,&nbsp;nums:&nbsp;List[int])</span>&nbsp;-&gt;&nbsp;List[int]:</span><br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;n&nbsp;=&nbsp;len(nums)<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;result&nbsp;=&nbsp;[<span class="hljs-number" style="color: #d19a66; line-height: 26px;">-1</span>]&nbsp;*&nbsp;n<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;stack&nbsp;=&nbsp;[]<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span class="hljs-comment" style="color: #5c6370; font-style: italic; line-height: 26px;">#&nbsp;最底下最大</span><br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">for</span>&nbsp;i&nbsp;<span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">in</span>&nbsp;range(<span class="hljs-number" style="color: #d19a66; line-height: 26px;">2</span>&nbsp;*&nbsp;n):<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span class="hljs-comment" style="color: #5c6370; font-style: italic; line-height: 26px;">#&nbsp;注意i&nbsp;%&nbsp;n是当前数字的真实索引,&nbsp;因为这里采用了遍历2倍数组长度的做法</span><br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span class="hljs-comment" style="color: #5c6370; font-style: italic; line-height: 26px;">#&nbsp;当栈不为空，且当前元素比顶部元素大,&nbsp;则顶部元素要出栈，因为要保证栈单调递减</span><br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">while</span>&nbsp;len(stack)&nbsp;&gt;&nbsp;<span class="hljs-number" style="color: #d19a66; line-height: 26px;">0</span>&nbsp;<span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">and</span>&nbsp;nums[i%n]&nbsp;&gt;&nbsp;nums[stack[<span class="hljs-number" style="color: #d19a66; line-height: 26px;">-1</span>]]:<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span class="hljs-comment" style="color: #5c6370; font-style: italic; line-height: 26px;">#&nbsp;stack.pop()让顶部元素出栈，并且返回顶部元素的索引，当前元素&gt;顶部元素，所以赋值给result[顶部元素]</span><br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;result[stack.pop()]&nbsp;=&nbsp;nums[i%n]<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;stack.append(i%n)<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span class="hljs-keyword" style="color: #c678dd; line-height: 26px;">return</span>&nbsp;result<br><br></code></pre>
<h3 data-tool="mdnice编辑器" style="margin-bottom: 15px; padding: 0px; font-weight: bold; color: black; font-size: 20px; margin-top: 1.2em;"><span style="background-image: url(https://files.mdnice.com/koala-3.png); background-size: 100% 100%; background-repeat: no-repeat; display: inline-block; width: 16px; height: 15px; line-height: 15px; margin-bottom: -1px;"></span><span class="prefix" style="display: none;"></span><span class="content" style="font-size: 17px; font-weight: bold; display: inline-block; margin-left: 8px; color: #48b378;">参考题解</span><span class="suffix" style="display: none;"></span></h3>
<p data-tool="mdnice编辑器" style="font-size: 16px; padding-bottom: 8px; margin: 0; padding-top: 1em; color: rgb(74,74,74); line-height: 1.75em;"><a href="https://leetcode-cn.com/problems/next-greater-element-ii/solution/dong-hua-jiang-jie-dan-diao-zhan-by-fuxu-4z2g/" style="word-wrap: break-word; font-weight: bold; color: #48b378; text-decoration: none; border-bottom: 1px solid #48b378;">leetcode动画题解</a></p>
</section>
                </div>
                

                
                    <div class="next-post">
                        <div class="next">下一篇</div>
                        <a href="https://woodywrx.gitee.io/blog/post/mei-ri-yi-ti-20210305-pan-duan-neng-fou-xing-cheng-deng-chai-shu-lie/">
                            <h3 class="post-title">
                                每日一题20210305判断能否形成等差数列
                            </h3>
                        </a>
                    </div>
                
                
                    <span id="/blog/post/mei-ri-yi-ti-20210306503-xia-yi-ge-geng-da-yuan-su-ii/"
                          class="leancloud_visitors" data-flag-title="每日一题20210306（503. 下一个更大元素 II）">
                <em class="post-meta-item-text">阅读量 </em>
                <i class="leancloud-visitors-count">0</i>
            </span>
                
                
                    

	<div id="vcomments" style="width: 100%;max-width:1000%;padding:2.5%"></div>



                

            </div>

        </div>
    </div>
</div>

<script src="https://unpkg.com/aos@next/dist/aos.js"></script>
<script type="application/javascript">

AOS.init();

var app = new Vue({
  el: '#app',
  data: {
    menuVisible: false,
  },
})

</script>






<script src='https://cdn.jsdelivr.net/npm/valine/dist/Valine.min.js'></script>
<script>
    new Valine({
        el: '#vcomments',
        appId: 'fT8wvEVNtx1cOcCQEs7rVwnV-gzGzoHsz',
        appKey: 'xV6aDHKSkLfP7u0cBRIzpmcy',
        avatar: '',
        pageSize: 5,
        recordIp: true,
        placeholder: 'Just Go Go',
        visitor: true,
    });
</script>
<script async src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>
</body>
</html>
